Go 实现队列
拿 Golang 刷题遇到的最大的麻烦就是它不像 Java 那样提供了必须的数据结构，很多时候都需要自己实现
拿 slice 当 queue
// 初始化一个队里：
var queue []int
// 入队一个元素：
queue = append(queue, 1)
// 出队一个元素：
if len(queue) > 1 {
queue = queue[1:]
}
但你会不会有一点觉得 queue = queue[1:] 这样的写法有一点挫？
白白浪费掉了 slice 前端元素的内存，和队列的假溢出问题有点像，当然 slice 会自动扩容，并不会发生假溢出，且每次扩容时会重新开辟新数组，拷贝元素到新数组时并不会拷贝被弃用的元素，所以内存的浪费还是在可控的范围内的。
// 一个空的 cap 为 5 的 slice
queue := make([]int, 0, 5) // _ _ _ _ _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 输出 len(queue): 0, cap(queue): 5, queue: []
// 入队一个元素
queue = append(queue, 1) // [1] _ _ _ _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 输出 len(queue): 1, cap(queue): 5, queue: [1]
// 再入队一个元素
queue = append(queue, 2) // [1 2] _ _ _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 输出 len(queue): 2, cap(queue): 5, queue: [1 2]
// 出队一个元素
queue = queue[1:] // 1 [2] _ _ _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 输出 len(queue): 1, cap(queue): 4, queue: [2]
// 再入队三个元素
queue = append(queue, 3, 4, 5) // 1 [2 3 4 5]
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 输出 len(queue): 4, cap(queue): 4, queue: [2 3 4 5]
// 出队二个元素
queue = queue[2:] // 1 2 3 [4 5]
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 输出 len(queue): 2, cap(queue): 2, queue: [4 5]
// 再入队一个元素，触发 slise 的扩容，根据扩容策略，此时 slice cap 为 2，翻倍为 4
queue = append(queue, 6) // // [4 5 6] _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 输出 len(queue): 3, cap(queue): 4, queue: [4 5 6]
但是当不断地入队出队，slice 的需要反复扩容，这也可能造成一定的 CPU 消耗。
拿 list 当 queue
这里的 list 指的是 golang 内置的包 container/list，是这是一个双向链表的实现
// 初始化一个队里：
queue := list.New()
// 入队一个元素：
queue.PushBack(1)
// 出队一个元素：
if queue.Len() > 1 {
queue.Remove(queue.Front())
}
因为 list 是双向链表，所以无需考虑扩容的问题
使用 slice 实现 Stack
var stack []string
stack = append(stack, "world!") // Push
stack = append(stack, "Hello ")
for len(stack) > 0 {
n := len(stack) - 1 // Top element
fmt.Print(stack[n])
stack = stack[:n] // Pop
}
基本的思路就是这样，但是在实际项目中不要这么使用，这么做会带来内存泄漏的风险。
使用 list 实现 Stack
import "container/list"
// 初始化
stack := list.New()
// 入栈
stack.PushBack(123)
// 出栈 返回的数据是结构类型 Value 需要断言成相应的类型
num2 = stack.Back()
stack.Remove(num2)
// 如果确定是非 nil，可以直接
stack.Remove(stack.Back()) // Pop